package com.leetcode.算法策略相关.动态规划;

/**
 * @author: xiaomi
 * @date: 2021/2/6
 * @description: 300. 最长递增子序列
 * https://leetcode-cn.com/problems/longest-increasing-subsequence/
 * 这道题不能直接求解，感觉有点脑筋急转弯的味道！
 */
public class B_300_最长递增子序列 {

	public static void main(String[] args) {

	}


	/**
	 * to be honest 依然看不出来 dp 的状态方程和 转移方程。
	 * --
	 * 所以我采用遍历的方式
	 * 问题在于这道题连暴力解法都不好写。
	 * --
	 * DP:
	 * 1.状态方程确定：以 i 为结束的最长上升子序列的大小；
	 * 2.状态转移方程：dp[i]=max(dp[0],dp[1],dp[2]...dp[i-1])+ nums[i]>nums[x]?1:0
	 * 上面这个状态方程不太好写，于是改为：
	 * if(nums[i]>nums[j])
	 * dp[i]=max(dp[i], dp[j]+1)
	 *
	 * @param nums
	 * @return
	 */
	public int lengthOfLISBy(int[] nums) {
		int len = nums.length;
		int[] dp = new int[len];
		dp[0] = 1;
		int index = 0;
		int max = dp[0];
		for (int i = 1; i < len; i++) {
			dp[i] = 1;
			for (int j = 0; j < i; j++) {
				if (nums[i] > nums[j]) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
			max = Math.max(max, dp[i]);
		}
		return max;
	}

	/**
	 * 子序列跟子数组是不一样的：可以删除子数组中的元素也是子序列
	 *
	 * @param nums
	 * @return
	 */
	public int lengthOfLISByDP(int[] nums) {
		int len = nums.length;
		//设计：以 i 为底的子序列的长度
		int[] dp = new int[len];
		int max = 1;
		dp[0] = 1;
		for (int i = 1; i < len; i++) {
			dp[i] = 1;
			for (int j = 0; j < i; j++) {
				if (nums[i] > nums[j]) {
					//符合 上升
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
			max = Math.max(max, dp[i]);
		}
		return max;
	}

	/**
	 * 贪心算法
	 * 如果想让递增子序列更长，就是要让子序列中每一个元素的值更小！
	 * 定义 tails 数组：
	 * tails[i] 表示长度为 i+1 时的最小的值。
	 * 这样也是 O(n^2)
	 * 但是由于 tails 是一个递增序列，所以可以进行 二分查找的优化，那么最终就是：
	 * O(NLogN)
	 * @param nums
	 * @return
	 */
	public int lengthOfLISByGreedy(int[] nums) {
return 1;
	}
}
